package example3;

import java.util.*;

//207. 课程表
public class LeetCode207 {
    public static void main(String[] args) {

    }
}

class Solution207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int plen = prerequisites.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = null;
        for(int i=0;i<plen;i++){
            list = map.get(prerequisites[i][0]);
            if(list == null){
                list = new ArrayList<>();
            }
            list.add(prerequisites[i][1]);
            map.put(prerequisites[i][0],list);
        }
        //是否可以修，0未遍历，1搜索中，2完成搜索能修
        int[] can = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            if(can[i] != 2){
                if(!canFinishNode(i,map,can)){
                    return false;
                }
            }
        }
        return true;
    }

    //判断第n个课程是否能修
    public boolean canFinishNode(Integer n,Map<Integer,List<Integer>> map,int[] can){
        List<Integer> list = null;
        list = map.get(n);
        //当前节点没有先修可能，true
        if(list == null)    return true;
        //当前节点已经是搜索处在搜索中了，说明成环了，false
        if(can[n] == 1)  return false;
        //如果这条链路到当前节点的时候还没有成环，那么就判断当前节点课程是否可以修，也就是是否搜索完成
        //如果当前课程可以修的话，那么就向它的父节点课程返回true。
        //这种判断用于应对那些先遍历了子节点，但是还没遍历父节点的情况，
        //加上这个判断，就可以减少遍历的次数，防止遍历父节点时有重复遍历子节点
        if(can[n] == 2)  return true;
        //然后直接将当前课程设置为搜索中
        can[n] = 1;
        //如果当前课程想要能修，那么它的所有先修可能都必须能修。
        for(int i=0;i<list.size();i++){
            if(!canFinishNode(list.get(i),map,can)) return false;
        }
        //所有的先修课都能修，当前课程设置为能修
        can[n] = 2;
        return true;
    }
}

/*
//方法三：用3种状态，可以少用一个集合
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int plen = prerequisites.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = null;
        for(int i=0;i<plen;i++){
            list = map.get(prerequisites[i][0]);
            if(list == null){
                list = new ArrayList<>();
            }
            list.add(prerequisites[i][1]);
            map.put(prerequisites[i][0],list);
        }
        //是否可以修，0未遍历，1搜索中，2完成搜索能修
        int[] can = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            if(can[i] != 2){
                if(!canFinishNode(i,map,can)){
                    return false;
                }
            }
        }
        return true;
    }

    //判断第n个课程是否能修
    public boolean canFinishNode(Integer n,Map<Integer,List<Integer>> map,int[] can){
        List<Integer> list = null;
        list = map.get(n);
        //当前节点没有先修可能，true
        if(list == null)    return true;
        //当前节点已经是搜索处在搜索中了，说明成环了，false
        if(can[n] == 1)  return false;
        //如果这条链路到当前节点的时候还没有成环，那么就判断当前节点课程是否可以修，也就是是否搜索完成
        //如果当前课程可以修的话，那么就向它的父节点课程返回true。
        //这种判断用于应对那些先遍历了子节点，但是还没遍历父节点的情况，
        //加上这个判断，就可以减少遍历的次数，防止遍历父节点时有重复遍历子节点
        if(can[n] == 2)  return true;
        //然后直接将当前课程设置为搜索中
        can[n] = 1;
        //如果当前课程想要能修，那么它的所有先修可能都必须能修。
        for(int i=0;i<list.size();i++){
            if(!canFinishNode(list.get(i),map,can)) return false;
        }
        //所有的先修课都能修，当前课程设置为能修
        can[n] = 2;
        return true;
    }*/

/*
//自己想的方法二：hashSet改造
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int plen = prerequisites.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = null;
        for(int i=0;i<plen;i++){
            list = map.get(prerequisites[i][0]);
            if(list == null){
                list = new ArrayList<>();
            }
            list.add(prerequisites[i][1]);
            map.put(prerequisites[i][0],list);
        }
        boolean[] can = new boolean[numCourses];
        Set<Integer> visited = null;
        for(int i=0;i<numCourses;i++){
            if(!can[i]){
                visited = new HashSet<>(numCourses);
                if(!canFinishNode(i,map,can,visited)){
                    return false;
                }
            }
        }
        return true;
    }

    //判断第n个课程是否能修
    public boolean canFinishNode(Integer n,Map<Integer,List<Integer>> map,boolean[] can,
                                 Set<Integer> visited){
        List<Integer> list = null;
        list = map.get(n);
        //当前节点没有先修可能，true
        if(list == null)    return true;
        //当前节点已在当前先修链路中被访问过了，说明成环了，false
        if(visited.contains(n))  return false;
        //如果这条链路到当前节点的时候还没有成环，那么就判断当前节点课程是否可以修，
        //如果当前课程可以修的话，那么就向它的父节点课程返回true。
        //这种判断用于应对那些先遍历了子节点，但是还没遍历父节点的情况，
        //加上这个判断，就可以减少遍历的次数，防止遍历父节点时有重复遍历子节点
        if(can[n])  return true;
        //然后直接将当前课程设置为可以修，因为如果后面成环了，那么会直接返回false，所有的校验都会结束，
        //那时can数组也没用了。如果没有成环，那么就不会返回false，当前课程也是可以修的can[n]=true也
        //没问题，而且还可以给别的节点校验时使用。
        can[n] = true;
        visited.add(n);
        //如果当前课程想要能修，那么它的所有先修可能都必须能修。
        for(int i=0;i<list.size();i++){
            if(!canFinishNode(list.get(i),map,can,visited)) return false;
        }
        visited.remove(n);
        return true;
    }*/

/*
//自己想的方法一：不能解决1 --> 2, 2 --> 3, 1 --> 3的情况
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int plen = prerequisites.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = null;
        for(int i=0;i<plen;i++){
            list = map.get(prerequisites[i][0]);
            if(list == null){
                list = new ArrayList<>();
            }
            list.add(prerequisites[i][1]);
            map.put(prerequisites[i][0],list);
        }
        boolean[] can = new boolean[numCourses];
        boolean[] visited = null;
        for(int i=0;i<numCourses;i++){
            if(!can[i]){
                visited = new boolean[numCourses];
                if(!canFinishNode(i,map,can,visited)){
                    return false;
                }
            }
        }
        return true;
    }

    //判断第n个课程是否能修
    public boolean canFinishNode(int n,Map<Integer,List<Integer>> map,boolean[] can,
                                 boolean[] visited){
        List<Integer> list = null;
        list = map.get(n);
        //当前节点没有先修可能，true
        if(list == null)    return true;
        //当前节点已在当前先修链路中被访问过了，说明成环了，false
        if(visited[n])  return false;
        if(can[n])  return true;
        //然后直接将当前课程设置为可以修，因为如果后面成环了，那么会直接返回false，所有的校验都会结束，
        //那时can数组也没用了。如果没有成环，那么就不会返回false，当前课程也是可以修的can[n]=true也
        //没问题，而且还可以给别的节点校验时使用。
        can[n] = true;
        visited[n] = true;
        boolean finish = true;
        //如果当前课程想要能修，那么它的所有先修可能都必须能修。
        for(int i=0;i<list.size();i++){
//            finish = finish && canFinishNode(list.get(i),map,can,visited);
            if(!canFinishNode(list.get(i),map,can,visited)) return false;
        }
        return true;
    }*/


